/**
 * Search.java
 * @author: liuex
 * 2008-1-9 ����10:44:44
 *
 * note: 
 */
package org.lex.utils;

import java.util.Comparator;

import javax.swing.ListModel;
import javax.swing.tree.TreeNode;

public class BinarySearch {
	/**
	 * Searches the specified <code>range</code> for the specified
	 * <code>key</code> using the binary search algorithm. The range must be
	 * sorted prior to making this call. If it is not sorted, the results are
	 * undefined. If the range contains multiple elements with the specified
	 * value, there is no guarantee which one will be found.<code>NULL</code>
	 * value is not allowed
	 * 
	 * @param <T>
	 * @param range
	 *            the range to be searched
	 * @param c
	 * @param key
	 *            the value to be searched for
	 * @return index of the search key, if it is contained in the range;
	 *         otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>. The
	 *         <i>insertion point</i> is defined as the point at which the key
	 *         would be inserted into the range: the index of the first element
	 *         greater than the key, or <tt>range.endPosition()</tt> if all
	 *         elements in the range are less than the specified key. Note that
	 *         this guarantees that the return value will be &gt;= 0 if and only
	 *         if the key is found.
	 */
	public static <T> int search(Range<T> range, T key, Comparator<T> c) {
		int low = range.startPosition();
		int high = range.endPosition() - 1;
		int mid = 0;
		while (low <= high) {
			mid = (low + high) / 2;
			int cmp = c.compare(range.getValue(mid), key);
			if (0 == cmp)
				return mid;
			else if (cmp > 0)
				high = mid - 1;
			else
				low = mid + 1;
		}
		return -(low + 1);
	}

	public static <T extends Comparable<T>> int search(Range<T> range, T key) {
		return search(range, key, Comparators.newComparator(key));
	}

	public static int search(TreeNode root, String childname) {
		return search(Ranges.wrap(root), childname);
	}

	public static int search(TreeNode root, TreeNode child, Comparator<TreeNode> cp) {
		return search(Ranges.wrapTreeNode(root), child, cp);
	}

	public static int search(final ListModel model, Object item) {
		return search(Ranges.wrap(model), item, Comparators.stringComparator());
	}

	public static void main(String[] args) {
		Integer[] a = { 2, 5, 9, 20, 50, 100 };
		Integer[] b = { 5 };
		System.out.println(search(Ranges.wrap(a, 0, a.length), 50));
		System.out.println(search(Ranges.wrap(b, 0, b.length), 4));
	}
}
